<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Trie树的实现</title>
</head>

<body>
  <!-- <script>
    var Trie = function () {
      this.children = {};
    };
    Trie.prototype.insert = function (word) {
      let nodes = this.children;
      for (const ch of word) {//循环word
        console.log(ch, "| ch");
        if (!nodes[ch]) {//当前字符不在子节点中 则创建一个子节点到children的响应位置
          nodes[ch] = {};
        }
        nodes = nodes[ch];//移动指针到下一个字符子节点
      }
      nodes.isEnd = true;//字符是否结束
    };
    Trie.prototype.searchPrefix = function (prefix) {
      let nodes = this.children;
      console.log(nodes, "| nodes");
      for (const ch of prefix) {//循环前缀
        if (!nodes[ch]) {//当前字符不在子节点中 直接返回false
          return false;
        }
        nodes = nodes[ch];//移动指针到下一个字符子节点
      }
      return nodes;//返回最后的节点
    }
    Trie.prototype.search = function (word) {
      const nodes = this.searchPrefix(word);
      //判断searchPrefix返回的节点是不是字符串的结尾的字符
      return nodes !== undefined && nodes.isEnd !== undefined;
    };
    Trie.prototype.startsWith = function (prefix) {
      const nodes = this.searchPrefix(prefix);
      return nodes !== undefined
    };



    let trie = new Trie();
    trie.insert("apple");
    console.log(trie.search("apple"));// 返回 True
    // console.log(trie.search("app"));     // 返回 False
    // console.log(trie.startsWith("app")); // 返回 True
    // trie.insert("pencile");
    // console.log(trie.search("app"));     // 返回 True
    // console.log(trie.startsWith("p"));
  </script> -->


  <script>
    // let arr = [
    //   { id: 1, name: '部门1', pid: 0 },
    //   { id: 2, name: '部门2', pid: 1 },
    //   { id: 3, name: '部门3', pid: 1 },
    //   { id: 4, name: '部门4', pid: 3 },
    //   { id: 5, name: '部门5', pid: 4 },
    // ]


    // 假设有如下数据，需要转成树结构：
    let arr = [
      { id: 1, parentId: null, name: 'a' },
      { id: 2, parentId: null, name: 'b' },
      { id: 3, parentId: 1, name: 'c' },
      { id: 4, parentId: 2, name: 'd' },
      { id: 5, parentId: 1, name: 'e' },
      { id: 6, parentId: 3, name: 'f' },
      { id: 7, parentId: 4, name: 'g' },
      { id: 8, parentId: 7, name: 'h' },
    ]

    // 定义最终输出的数组
    let trees = []

    // 定义一个map
    let map = new Map()

    // 遍历源数组，给map添加数据
    for (let v of arr) {
      // set(key,value)方法：	向当前Map对象中添加一个值，返回的Map对象，所以支持链式写法
      map.set(v.id, v)
    }

    for (let v of arr) {
      const pId = v.parentId

      // 方法has(key) 返回一个bool值，用来表明map 中是否存在指定元素.
      // 如果map中不存在当前元素parentId，则该元素为根元素，当前数据针对null，是不存在的
      if (!map.has(pId)) {
        // push的对象是引用类型(浅拷贝)
        trees.push(v)
      }

      // 如果map中存在 当前元素的parentId，则该元素不为根元素
      else {
        // get(key)	通过key找到value，如果找不到，返回undefined
        const parent = map.get(pId)

        // instanceof方法：用于判断一个变量是否某个对象的实例
        // 这里的意思是：如果parent没有children这个字段或者不是一个数组，则手动添加一个children属性为空数组
        !(parent.children instanceof Array) && (parent.children = [])

        parent.children.push(v)
      }
    }
    console.log(trees)




    var menu_list = [{
      id: '1',
      menu_name: '设置',
      menu_url: 'setting',
      parent_id: 0
    }, {
      id: '1-1',
      menu_name: '权限设置',
      menu_url: 'setting.permission',
      parent_id: '1'
    }, {
      id: '1-1-1',
      menu_name: '用户管理列表',
      menu_url: 'setting.permission.user_list',
      parent_id: '1-1'
    }, {
      id: '1-1-2',
      menu_name: '用户管理新增',
      menu_url: 'setting.permission.user_add',
      parent_id: '1-1'
    }, {
      id: '1-1-3',
      menu_name: '角色管理列表',
      menu_url: 'setting.permission.role_list',
      parent_id: '1-1'
    }, {
      id: '1-2',
      menu_name: '菜单设置',
      menu_url: 'setting.menu',
      parent_id: '1'
    }, {
      id: '1-2-1',
      menu_name: '菜单列表',
      menu_url: 'setting.menu.menu_list',
      parent_id: '1-2'
    }, {
      id: '1-2-2',
      menu_name: '菜单添加',
      menu_url: 'setting.menu.menu_add',
      parent_id: '1-2'
    }, {
      id: '2',
      menu_name: '订单',
      menu_url: 'order',
      parent_id: 0
    }, {
      id: '2-1',
      menu_name: '报单审核',
      menu_url: 'order.orderreview',
      parent_id: '2'
    }, {
      id: '2-2',
      menu_name: '退款管理',
      menu_url: 'order.refundmanagement',
      parent_id: '2'
    }
    ]
    /**
 * 将一维的扁平数组转换为多层级对象
 * @param  {[type]} list 一维数组，数组中每一个元素需包含id和parent_id两个属性 
 * @return {[type]} tree 多层级树状结构
 */
    function buildTree(list) {
      let temp = {};
      let tree = {};
      for (let i in list) {
        temp[list[i].id] = list[i];
      }
      for (let i in temp) {
        if (temp[i].parent_id) {
          if (!temp[temp[i].parent_id].children) {
            temp[temp[i].parent_id].children = new Object();
          }
          temp[temp[i].parent_id].children[temp[i].id] = temp[i];
        } else {
          tree[temp[i].id] = temp[i];
        }
      }
      return tree;
    }
    console.log(buildTree(menu_list));
  </script>



</body>

</html>